package com.platform.modules.alg.alglib.poj3321;


public class Poj3321 {
    private int maxn = 100000;
    int N, q;
    int c[] = new int[maxn];
    int a[] = new int[maxn];
    int L[] = new int[maxn];
    int R[] = new int[maxn];
    int head[] = new int[maxn];
    int cnt;
    int dfn;

    edge E[] = new edge[2 * maxn];

    public String output = "";

    void adde(int u, int v) {
        E[++cnt].u = u;
        E[cnt].v = v;
        E[cnt].next = head[u];
        head[u] = cnt;
    }

    int lowbit(int x) {
        return x & (-x);
    }

    void add(int i, int v) {
        for (; i <= N; i += lowbit(i))
            c[i] += v;
    }

    int sum(int i) {
        int ans = 0;
        for (; i > 0; i -= lowbit(i)) {
            ans += c[i];
        }
        return ans;
    }

    void init() {
        for (int i = 0; i < E.length; i++) {
            E[i] = new edge();
        }
        cnt = 0;
        dfn = 1;
        for (int i = 1; i <= N; i++) {
            a[i] = 1;
            add(i, 1);
        }
    }

    void dfs(int u, int fa) {
        L[u] = dfn++;
        for (int i = head[u]; i > 0; i = E[i].next) {
            int v = E[i].v;
            if (v == fa) continue;
            dfs(v, u);
        }
        R[u] = dfn - 1;
    }


    public String cal(String input) {
        String[] line = input.split("\n");
        N = Integer.parseInt(line[0]);
        int u, v;
        init();
        for (int i = 1; i < N; i++) {
            String[] edge = line[i].split(" ");
            u = Integer.parseInt(edge[0]);
            v = Integer.parseInt(edge[1]);
            adde(u, v);
        }
        dfs(1, 1);

        q = Integer.parseInt(line[N]);

        for (int i = 1; i <= q; i++) {
            String[] query = line[N + i].split(" ");
            v = Integer.parseInt(query[1]);
            if (query[0].charAt(0) == 'C') {
                if (a[L[v]] > 0)
                    add(L[v], -1);
                else
                    add(L[v], 1);
                a[L[v]] ^= 1;
            } else {
                int s1 = sum(R[v]);
                int s2 = sum(L[v] - 1);
                output += (s1 - s2) + "\n";
            }
        }
        return output;
    }
}


class edge {
    int u, v;
    int next;
}
